class Solution {
public:
    int sqrt(int x) {
        if (x==0) return 0;
        int h=1, t=x, ret;
        while (h<=t) {
            int w=(h+t)/2;
            if (w<=x/w) {
                ret=w;
                h=w+1;
            } else t=w-1;
        }
        return ret;
    }
};
